/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-10-09
 * Time:20:39
 */

//单链表练习题
public class Test {
    public static void main(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(11);
        list.addLast(21);
        list.addLast(31);
        list.addLast(41);
        list.addLast(51);

        list.createLoop();
        MySingleList.ListNode startCycleNode = list.detectCycle();
        System.out.println(startCycleNode.val);//31
    }
    public static void main10(String[] args) {
        MySingleList list = new MySingleList();
        list.addLast(11);
        list.addLast(21);
        list.addLast(31);
        list.addLast(41);
        list.addLast(51);

        list.createLoop();
        boolean ret = list.hasCycle();
        System.out.println(ret);
    }
    //设置两个链表相交的节点
    public static void createCut(MySingleList.ListNode headA,MySingleList.ListNode headB) {
        //headB（短链表）尾节点的next指向改成指向headA（长链表）的某一个节点
        headB.next.next.next = headA.next.next;
    }
    public static void main9(String[] args) {
        //相交链表
        MySingleList list1 = new MySingleList();
        list1.addLast(11);
        list1.addLast(21);
        list1.addLast(31);
        list1.addLast(41);
        list1.addLast(51);

        MySingleList list2 = new MySingleList();
        list2.addLast(12);
        list2.addLast(23);
        list2.addLast(34);

        createCut(list1.head,list2.head);

        MySingleList.ListNode ret = MySingleList.getIntersectionNode(list1.head,list2.head);
        System.out.println("两个链表相交的节点值为" + ret.val);
        list1.display2(ret);//31 41 51
        list2.display2(ret);//31 41 51
        list1.display();//11 21 31 41 51
        list2.display();//12 23 34 31 41 51
    }
    public static void main8(String[] args) {
        //回文链表
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(2);
        list.addLast(1);
        list.display();

        boolean ret = list.isPalindrome();
        System.out.println(ret);
    }
    public static void main7(String[] args) {
        //分割链表
        MySingleList list = new MySingleList();
        list.addLast(34);
        list.addLast(23);
        list.addLast(45);
        list.addLast(12);
        list.addLast(56);
        list.display();//34 23 45 12 56

        MySingleList.ListNode head = list.partition(45);
        list.display2(head);//34 23 12 45 56
    }
    public static void main6(String[] args) {
        //合并两个有序链表
        MySingleList list1 = new MySingleList();
        list1.addLast(1);
        list1.addLast(2);
        list1.addLast(4);
        MySingleList list2 = new MySingleList();
        list2.addLast(1);
        list2.addLast(3);
        list2.addLast(4);

        MySingleList list = new MySingleList();

        MySingleList.ListNode newHead = list.mergeTwoList(list1.head,list2.head);
        list1.display2(newHead);
    }
    //合并两个有序链表
    //将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
    public static MySingleList.ListNode mergeTwoList(MySingleList.ListNode headA,
                                                     MySingleList.ListNode headB) {
        MySingleList.ListNode newHead = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmp = newHead;
        while (headA != null && headB != null) {
            if (headA.val <headB.val) {
                tmp.next = headA;
                headA = headA.next;
                tmp = tmp.next;
            }else {
                tmp.next = headB;
                headB = headB.next;
                tmp = tmp.next;
            }
        }
        if (headA != null) {
            tmp.next = headA;
        }
        if (headB != null) {
            tmp.next = headB;
        }
        return newHead.next;
    }
    public static void main5(String[] args) {
        //合并两个有序链表
        MySingleList list1 = new MySingleList();
        MySingleList list2 = new MySingleList();

        list1.addLast(1);
        list1.addLast(2);
        list1.addLast(4);

        list2.addLast(1);
        list2.addLast(3);
        list2.addLast(4);

        MySingleList.ListNode newHead = mergeTwoList(list1.head,list2.head);
        list2.display2(newHead);//1 1 2 3 4 4
    }
    public static void main4(String[] args) {
        //返回链表倒数第k个节点
        MySingleList list = new MySingleList();
        list.addLast(25);
        list.addLast(36);
        list.addLast(18);
        list.addLast(42);
        list.addLast(51);
        list.display();//25 36 18 42 51

        int ret = list.kthToList(3);
        System.out.println(ret);//18
        int ret1 = list.kthToList(2);
        System.out.println(ret1);//42
        int ret2 = list.kthToList(5);
        System.out.println(ret2);//25
        int ret3 = list.kthToList(1);
        System.out.println(ret3);//51

        MySingleList list1 = new MySingleList();
        list1.addLast(25);
        list1.addLast(36);
        list1.addLast(18);
        list1.addLast(42);
        list1.display();

        int ret4 = list1.kthToList(3);
        System.out.println(ret4);
    }
    public static void main3(String[] args) {
        //链表的中间节点
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(5);
        list.display();
        System.out.print("链表中的节点是奇数——打印中间节点及之后的节点数据：");
        MySingleList.ListNode middle = list.middleNode();
        list.display2(middle);//3 4 5

        MySingleList list1 = new MySingleList();
        list1.addLast(1);
        list1.addLast(2);
        list1.addLast(3);
        list1.addLast(4);
        list1.addLast(5);
        list1.addLast(6);
        list1.display();
        System.out.print("链表中的节点是偶数——打印中间节点及之后的节点数据：");
        MySingleList.ListNode middle1 = list1.middleNode();
        list1.display2(middle1);//4 5 6
    }
    public static void main2(String[] args) {
        //反转链表
        MySingleList list = new MySingleList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.addLast(5);
        System.out.print("反转前链表：");
        list.display();

        System.out.print("反转后链表：");
        MySingleList.ListNode head = list.reverseList();
        list.display2(head);
    }
    public static void main1(String[] args) {
        //移除链表元素
        MySingleList list = new MySingleList();
        list.addLast(23);
        list.addLast(23);
        list.addLast(26);
        list.addLast(23);
        list.addLast(65);
        list.display();//23 23 26 23 65

        MySingleList.ListNode head = list.removeElements(23);
        list.display2(head);//26 65
    }
}
